
class SlkTree
{

private    Stack       parse_stack;
private    Node        root;

SlkTree ()
{              
    root = null;
    parse_stack = new Stack ();
}

private 
class Node
{
    public 
    short    symbol;
    public 
    Node     parent,        // parent is the lhs of the production
             child,         // first symbol on rhs of production
             sibling,       // rest of the parent production is siblings
             left_sibling;  // to go backwards

    Node ( short    symbol )
    {
        this.symbol = symbol;
        this.parent = null;
        this.child = null;
        this.sibling = null;
        this.left_sibling = null;
    }
};

private 
class Stack
{
    private static final int    STACKSIZE = 1024;
    
    private Node[]    start;
    private int       top,
                      end;
    
    Stack () {
        start = new Node [STACKSIZE];
        top = STACKSIZE - 1;
        end = STACKSIZE;
    }
    
    public Node
    pop ()
    {
        Node  value = null;

        if ( top < end ) {
            value = start[top++];
        }
        return  value;
    }
    
    public void
    push ( Node  node )
    {
        start [--top] = node;
    }
};

private 
Node
make_LL_branch ( short       production_number )
{
    Node    prev = null;
    Node    child = null;
    short[] production = SlkParser.GetProductionArray ( production_number );
    short   rhs;
    int     length,
            index = 0,
            debug = 0,
            rhs_length;

    rhs_length = production [ index++ ] - 1;
    for ( length = rhs_length;  length > 0;  --length ) {
        rhs = production [ ++index ];               // skip over lhs
        if ( debug > 0 ) {
            System.out.println ( "rhs = " + SlkString.GetSymbolName ( rhs ) );
        } 
        if ( SlkParser.IsAction ( rhs ) ) {
            continue;                               // skip actions
        }
        prev = new Node ( rhs );
        child = prev;
        for ( --length;  length > 0;  --length ) {
            rhs = production [ ++index ];
            if ( debug > 0 ) {
                System.out.println ( "rhs = " + SlkString.GetSymbolName ( rhs ) + " " + rhs );
            }
            if ( SlkParser.IsAction ( rhs ) ) {
                continue;                           // skip actions
            }
            prev.sibling = new Node ( rhs );
            prev.sibling.left_sibling = prev;
            prev = prev.sibling;
        }
    }                 
    for (;  prev != null;  prev = prev.left_sibling ) {
        if ( SlkParser.IsNonterminal ( prev.symbol ) ) {
            parse_stack.push ( prev );                 // copy parsing pushes
        }              
    }

    return  child;
}

public
void
predict ( short  production_number )
{
    Node    parent;
    Node    child;
    short[] production = SlkParser.GetProductionArray ( production_number );

    System.out.println ( SlkString.GetProductionName ( production_number ) );

    if ( root == null ) {                                    // first call
        root = new Node ( production [ 1 ] );                // lhs    
        parse_stack.push ( root );
    }
    parent = parse_stack.pop ();
    child = make_LL_branch ( production_number );
    if ( child != null  &&  parent != null ) {
        parent.child = child;
        child.parent = parent;
    }
}

public
void
reduce ( short  production_number )
{
    Node    prev = null;
    Node    child = null;
    Node    this_child = null;
    short[] production = SlkParser.GetProductionArray ( production_number );
    short   rhs;
    int     length,
            index = 0,
            debug = 0,
            rhs_length;

    System.out.println ( SlkString.GetProductionName ( production_number ) );
    rhs_length = production [ index++ ] - 1;
    for ( length = rhs_length;  length > 0;  --length ) {
        rhs = production [ ++index ];               // skip over lhs
        if ( SlkParser.IsAction ( rhs ) ) {
            continue;                               // skip actions
        }
        prev = new Node ( rhs );
        this_child = prev;
        for ( --length;  length > 0;  --length ) {
            rhs = production [ ++index ];
            if ( SlkParser.IsAction ( rhs ) ) {
                continue;                           // skip actions
            }
            prev.sibling = new Node ( rhs );
            prev.sibling.left_sibling = prev;
            prev = prev.sibling;
        }
    }
    for (;  prev != null;  prev = prev.left_sibling ) {
        if ( SlkParser.IsNonterminal ( prev.symbol ) ) {
            child = parse_stack.pop ();
            if ( child != null ) {
                if ( debug > 0 ) {
                    System.out.println ( "pop :   " + SlkString.GetSymbolName ( child.symbol ) );
                } 
                prev.child = child;
                child.parent = prev;
            } else {
                if ( debug > 0 ) {
                    System.out.println ( "pop :   null" );
                } 
            }
        }
    }
    if ( this_child != null ) {
        if ( debug > 0 ) {
            System.out.println ( "push:   " + SlkString.GetSymbolName ( this_child.symbol ) );
        }
    } else {
        if ( debug > 0 ) {
            System.out.println ( "push:   null" );
        }              
    }
    parse_stack.push ( this_child );
    if ( production_number == 1 ) {
        root = new Node ( production [ 1 ] );                // lhs    
        root.child = this_child;
        if ( this_child != null ) {
            this_child.parent = root;
        }
    }
}

public void
show_tree ( Node   tree )
{
    Node  child,
          sibling;

    if ( tree == null ) {
        return;
    }
    System.out.println ( SlkString.GetSymbolName ( tree.symbol ) );

    child = tree.child;

    if ( child != null ) {
        show_tree ( child );
    
        for ( sibling = child.sibling;  sibling != null;  sibling = sibling.sibling ) {
            show_tree ( sibling );
        }
    }
}

public void
show_tree ()
{
    show_tree ( root );
}

public void
show_parse_derivation ()
{
    show_parse_derivation ( root );
}

public void
show_parse_derivation ( Node   tree )
{
    Node  child,
          sibling;

    if ( tree == null ) {
        return;
    }
    System.out.print ( SlkString.GetSymbolName ( tree.symbol ) + " -> ");

    child = tree.child;

    if ( child != null ) {
        System.out.print ( SlkString.GetSymbolName ( child.symbol ) + "  " );
        for ( sibling = child.sibling;  sibling != null;  sibling = sibling.sibling ) {
            System.out.print ( SlkString.GetSymbolName ( sibling.symbol ) + "  " );
        }
        System.out.println ();
    
        if ( SlkParser.IsNonterminal ( child.symbol ) ) {
            show_parse_derivation ( child );
        } 

        for ( sibling = child.sibling;  sibling != null;  sibling = sibling.sibling ) {
            if ( SlkParser.IsNonterminal ( sibling.symbol ) ) {
                show_parse_derivation ( sibling );
            }
        }
    } else { 
        System.out.println ();
    }
}


};
